import java.util.Arrays;

public class QuickSort {
    //方法中的三个参数：数组arr,要对arr[start]-arr[end]进行排序
    public static void sort(int [] arr,int start,int end){
        if (start<end) {//递归的出口，不能相等，不然会死递归
            //构建方法获取分区索引
            int index= getIndex(arr, start, end);
            sort(arr, start, index-1);//右半段进行排序
            sort(arr,index+1,end);//左半段进行排序
        }
    }
    private static int getIndex(int[] arr, int start, int end) {
       int i=start;
       int j=end;
       //定义一个基准数
       int x=arr[i];
       while (i<j){//循环开始
           //先从右到左比较
           while (i<j&&arr[j]>x){
                j--;
           }
           //如果比基准数小了，就进行填坑
           if (i<j){
               arr[i]=arr[j];//填到上一个坑位
               i++;
           }
           while (i<j&&arr[i]<=x){//从左往右比较
               i++;
           }
           if (i<j){
               arr[j]=arr[i];
               j--;
           }
       }//当上面的循环结束后把基准数填到最后一个坑位，也就以基准数为界，分成了左右两部分
        arr[i]=x;//填回基准数
        return i;//返回基准数的索引
    }

    public static void main(String[] args) {
        int [] arr={33,43,22,20,34,20,66};
        QuickSort.sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}
